package com.yitiao.data_algorithms.leetcode.editor.cn;

class EggDropWith2EggsAndNFloors {
    // 2023-04-25 17:43:55
    public static void main(String[] args) {
        Solution solution = new EggDropWith2EggsAndNFloors().new Solution();
    }

    /**
     * 函数定义：
     * dp(n, k)表示现在有n层楼需要验证，此时你手里有k个鸡蛋，返回此时的最小操作次数。
     *
     * base case：
     *
     * 如果没有楼层需要验证了(n == 0)，那你不管有几个鸡蛋都不用操作了。
     * 如果你手里只有一个鸡蛋了(k == 1)，那你只能从1楼开始试：1楼、2楼、...、n楼，共需要n次操作。
     * 状态转移：
     * 现在你手里有k个鸡蛋，接下来你要选一层楼扔鸡蛋，假设你选择了第i层楼，有两种情况：
     *
     * 鸡蛋碎了。你知道你要确定的f一定在[0, i-1]范围内了，也就是需要验证的楼层数变成了i-1，除此之外你还损失了一个鸡蛋，只剩下k-1个鸡蛋了。
     * 鸡蛋没碎。你知道你要确定的f一定在[i, n]范围内了，接下来需要验证的楼层数变成了n-i，并且你没有损失鸡蛋，你还有k个鸡蛋。
     * 题目的要求可以解释为：最坏情况下最少需要操作几次。最坏情况就是在这两种情况之间，选择那个需要操作次数最大的，再加上自己这一次扔鸡蛋的操作，
     * 也就是Math.max(dp(i-1, k-1), dp(n-i, k)) + 1，这个值就是你选择从第i层楼扔鸡蛋，最坏情况下需要的操作次数。
     *
     * dp(n, k)需要的操作次数，是你在所有楼层中选择一个最坏情况下需要的操作次数最小的楼层扔鸡蛋。
     * 所以需要遍历所有楼层，找到Math.min(res, Math.max(dp(i-1, k-1), dp(n-i, k)) + 1)。
     *
     * 为了避免重复计算，加上备忘录。
     */

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 备忘录
        int[][] memo;
        int res = Integer.MAX_VALUE;

        public int twoEggDrop(int n) {
            memo = new int[n+1][3];
            return dp(n,2);
        }

        public int dp(int n, int k) {
            // base case
            if (n == 0) {
                return 0;
            }
            if (k == 1) {
                return n;
            }
            if (memo[n][k] != 0) {
                return memo[n][k];
            }

            for (int i = 1; i <= n; i++) {
                res = Math.min(res,
                        Math.max(
                                dp(i - 1, k - 1),
                                dp(n - i, k)
                        ) + 1
                );
            }
            memo[n][k]=res;
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}